Content addressable memory devices (CAMs) are extremely valuable in providing associative look-up based on contents of incoming data. A CAM is pre-loaded with a predefined data set, consisting of data to be compared, and optionally, data to be output when a match is found, or alternatively, the address where the match is found. The output data or address can be output as an index to the requesting device, or both the address and data can be output for each match.
One problem incurred in using CAMs is that the construction of CAM chips requires multiples of the number of transistors to implement than standard read/write random access memory (RAM) would require. Thus, CAM chips are usually much smaller in depth size than RAM chips. Therefore, the capacity of a single CAM chip is frequently inadequate to provide for the necessary associative look-ups. Thus, it becomes necessary to use multiple CAM chips in some sort of cascaded or interconnected manner to provide greater depth.
Current binary CAM devices are using nearly 4 million transistors and have reached a memory size of 2k by 64. However, ATM and other applications require much more memory, such as 128k by 64. This requires the cascade of 64 of the 2K.times.4 CAMs. Current CAM devices present a propagation delay of around 80 ns per CAM. Cascading 64 CAMs creates a match propagation and data compare rate delay in the microseconds, which is unacceptable. High data rates which require 128k of CAM currently do not function effectively.
Another major problem with this approach is that there is a variable latency in this architecture, where the time taken to find a match is widely variable from associative look-up to associative look-up, due to the fact that there is uncertainty as to how many CAM chips in the chain will have to be accessed, one at a time in turn, until a match is found. CAM data input lines must be run in parallel to all of the chips in the cascade chain, and control logic and intercoupling must be provided between the multiple chips in the cascade chain.
This configuration is ineffective for handling multiple CAM matches for a single input. Data to be recognized by the system as acceptable in a CAM compare may be within a range. Therefore, it is efficient for a single CAM location to accommodate a range of data. This, however, can ultimately create multiple matches for a single input.
A parallel CAM configuration can handle multiple matches, but this requires an onerous subsystem and is very slow. Processing is normally done by the processor that loaded the data initially. Therefore, the system is at a standstill until the processor is free to load more data.
Another prior art attempt at greater CAM system efficiently couples the input and output data in parallel and chip control logic in series. Here each CAM chip passes the control down the line to the next chip serially. Naturally, the first CAM chip is idle while each successive chip compares the input word. As stated earlier, cascading 64 CAM chips for a required application creates a slow system due to this bottleneck. Each added CAM chip adds a propagation delay to the system, 64 chips would result in a minimum of 64 propagation delays between input and output. This type of system also requires a controller to synchronize the input and output of data since the combinational logic in the control creates indeterminate delays.
In a parallel data, serial control system, if no match is found in a first CAM chip, it passes data to the next chip and the first CAM chip goes idle until possibly every CAM location is checked. Allowing the majority of the circuits to idle during a search is an inefficient use of CAM chips. Current cascaded CAMs are also slow because after the lookup process is complete, masking, handshaking, and housekeeping is required and also performed in series. While these functions are being performed, the memory association circuits are again idle. No processing can occur until an output from the system is produced and new data is loaded. This so called "wait and see" approach is much too slow for the currently desired data transfer rate. Each added stage compounds the CAM lookup delay.
The prior art does not provide the capability of reading out multiple CAM location matches within a CAM chip or system. Indeed, multiple matches within an associative memory device create bus contention or bus conflict from every match location trying to output data at the same time.
In prior art systems, after attaining a memory address from the CAM lookup tables, auxiliary RAM is sometimes used to retrieve further needed data. This function requires external processing and a plurality of address lines. As CAM usage and memory requirements are growing, there is a need to increase density and to maintain or increase system speed, without the problems and shortcomings from idle circuits and unpredictable latency.